An M/G/1 Queuing System with Multiple Vacations to Assess the Performance of a Simplified Deficit Round Robin Model

摘要

Deficit Round-Robin (DRR) is a packet scheduling algorithmdevised for providing fair queuing in the presence of variable lengthpackets. Upper bounds on the buffer occupancy and scheduling delay ofa leaky bucket regulated flow have been proved to hold under DRR.However, performance bounds are important for real-time traffic suchas video or voice, whereas regarding data traffic average performanceindices are meaningful in most of the cases. In this paper we proposeand solve a specific worst-case model that enables us to calculatequantiles of the queue length distribution at any time (and henceaverage delays) as a function of the offered load, when the arrivalprocess is Poissonian. The model proposed is a discrete time discretestate Markov chain of M/G/1-Type, and hence we used the matrixanalytic methodology to solve it. The structure of the blocks belongingto the transition probability matrix is fully exploited. As a result of theabove exploitation an effective algorithm for computing the matrix Gis proposed. The algorithm consists in diagonalizing suitable matrixfunctions by means of Discrete Fourier Transform and in applyingNewton’s method.